package gold.digger;

import gold.utils.InputUtil;
import gold.vo.CodeDoc;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC240 {
    public long startExecuteTime = System.currentTimeMillis();


    public boolean searchMatrix(int[][] arr, int target) {
        if (null == arr || arr.length <= 0 || arr[0].length <= 0) {
            return false;
        }

        return searchMatrixRecur(arr, target, 0, 0, arr.length - 1, arr[0].length - 1);
    }

    public boolean searchMatrixRecur(int[][] arr, int target,
                                     int startX, int startY, int endX, int endY) {
        // check range validation.
        if (startX < 0 || startX > arr.length - 1 ||
                startY < 0 || startY > arr[0].length - 1 ||
                endX < 0 || endX > arr.length - 1 ||
                endY < 0 || endY > arr[0].length - 1) {
            return false;
        }

        while (endX - startX > 1 || endY - startY > 1) {
            int midX, midY;
            midX = startX + (endX - startX) / 2;
            midY = startY + (endY - startY) / 2;

            if (arr[midX][midY] == target) {
                return true;
            }

            if (arr[midX][midY] > target) {
                return searchMatrixRecur(arr, target, startX, startY, midX, midY) ||
                        searchMatrixRecur(arr, target, startX, midY, midX - 1, endY) ||
                        searchMatrixRecur(arr, target, midX, startY, endX, midY - 1);
            } else {
                return searchMatrixRecur(arr, target, startX, midY + 1, midX, endY) ||
                        searchMatrixRecur(arr, target, midX + 1, startY, endX, midY) ||
                        searchMatrixRecur(arr, target, midX, midY, endX, endY);
            }
        }

        return arr[startX][startY] == target || arr[startX][endY] == target
                || arr[endX][startY] == target || arr[endX][endY] == target;
    }

    public static void main(String[] args) throws Exception {
        LC240 an = new LC240();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[1,1]]");

        System.out.println(an.searchMatrix(arr, 1));


        Arrays.hashCode("".split(","));
        InputUtil.run();
        CodeDoc.run();
        System.out.println("\nanswer total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
